package com.mjlf.algorithms.sort;

/**
 * @auther a123
 * @create 2018-09-07 16:49
 * @desc 归并排序
 * 归并排序是在归并的操作上衍生出来的， 归并排序需要额外的存储空间
 * 归并排序是采用递归的方式，每次将当前数组划分类两份，然后分别对两份进行排序，最后将两份排好序的数组进行归并，
 * 然后被划分的子数组如果还可以划分，那么接着划分，如此递归，最后其实是两个数归并，
 */
public class MergeSort {

    public static void main(String[] args) {
        Integer[] elements = {1, 3, 2, 5, 3, 8, 4};
        shellSort(elements, 0, elements.length - 1);
        SortUtil.show(elements);
    }

    public static Comparable[] copyElements = null;

    public static void sort(Comparable[] elements) {
        copyElements = new Comparable[elements.length];
        sort(elements, 0, elements.length - 1);//需要注意的是这里是 element.length - 1;
    }

    /**
     * 归并排序， 元素数据大于15个，那么采用归并排序， 将数字拆分为两个子数组，否在将使用希尔排序
     *
     * @param elements
     * @param lo
     * @param hi
     */
    public static void sort(Comparable[] elements, int lo, int hi) {
        if ((hi - lo) <= 150) {
            shellSort(elements, lo, hi);
        } else {
            if(lo >= hi){
                return;
            }
            int mid = (hi + lo) / 2;
            sort(elements, lo, mid);
            sort(elements, mid + 1, hi);
            if (SortUtil.less(elements[mid + 1], elements[mid])) {
                merge(elements, lo, mid, hi);
            }
        }
    }

    /**
     * 归并两个数组
     *
     * @param elements
     * @param lo
     * @param mid
     * @param hi
     */
    public static void merge(Comparable[] elements, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;//注意这里是mid + 1，也就是第二个数组的起始位置
        for (int k = lo; k <= hi; k++) {
            copyElements[k] = elements[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                elements[k] = copyElements[j++];
            } else if (j > hi) {
                elements[k] = copyElements[i++];
            } else if (SortUtil.less(copyElements[i], copyElements[j])) {
                elements[k] = copyElements[i++];
            } else {
                elements[k] = copyElements[j++];
            }
        }
    }

    /**
     * 采用shell排序处理局部排序
     *
     * @param elements
     * @param lo
     * @param hi
     */
    public static void shellSort(Comparable[] elements, int lo, int hi) {
        int h = 1;
        while (h < (hi - lo) / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            for (int i = lo + h; i <= hi; i++) {
                Comparable indexElement = elements[i];
                int j = i;
                for (; j >= lo + h && SortUtil.less(indexElement, elements[j - h]); j -= h) {
                    elements[j] = elements[j - h];
                }
                elements[j] = indexElement;
            }
            h = h / 3;
        }
    }
}
